/**
 * 最大子序和
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 **/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


/**
 * Solution_1:分治法
 * 最大子序和可能有在左半部or右半部or横跨中部三种情况
 * 在左半部or右半部可递归求解
 * 横跨的情况求解 包含左半部分最后一个元素的最大和与包含右半部分第一个元素最大和之和
 **/
class Solution_1 {
public:
    int maxSubArray(vector<int>& nums) {
        // 求最大\最小值的题，初始值要设成理论上的最小\最大值
        int result = 0;
        int nums_end = nums.size() - 1;
        result = maxSum(nums, 0, nums_end);
        return result;
    }

    int maxSum(vector<int>& nums, int left, int right){
        // 数组中只有一个元素，结果即为该元素
        if(left == right){
            return nums[left];
        }
        
        int center = (left + right) / 2;
        // 递归求解左右部分最大和
        int leftmaxSum = maxSum(nums, left, center);
        int rightmaxSum = maxSum(nums, center+1, right);

        // 求解横跨情况的最大和
        // 求解包含左半部分最后一个元素的最大和，注意求和循环到左指针left停止
        int leftMax = INT_MIN;
        int leftSum = 0;
        for(int i=center; i>=left; i--){
            leftSum += nums[i];
            if(leftSum > leftMax){
                leftMax = leftSum;
            }
        }
        // 求解包含右半部分第一个元素的最大和，注意求和循环到右指针right停止
        int rigthMax = INT_MIN;
        int rightSum = 0;
        for(int j=center+1; j<=right; j++){
            rightSum += nums[j];
            if(rightSum > rigthMax){
                rigthMax = rightSum;
            }
        }

        // C++没有多数max函数，可以两两比较取最大
        int result = max(leftmaxSum, rightmaxSum);
        result = max(result, leftMax + rigthMax);
        return result;
    }
};


/**
 * Solution_2:动态规划(有最优子结构)
 * dp[i]代表到nums[i]为止，序列的最大子序列和
 * dp[0] = nums[0]
 * dp[i] = max(nums[i], dp[i-1]+nums[i]) 注意是连续子数组，一定是保留后面的值，舍弃前面的结果才能连续
 **/
class Solution_2{
public:
    int maxSubArray(vector<int>& nums){
        // // 方法1，用数组存储dp     
        // vector<int> dp(nums.size());
        // dp[0] = nums[0];
        // int result = nums[0];

        // for(int i=1; i<dp.size(); ++i){
        //     dp[i] = max(nums[i], dp[i-1] + nums[i]);
        //     // dp记录了遍历过程中的部分最大连续序列和，要在这之中找最大值
        //     result = max(result, dp[i]);
        // }
        // return result;
        
        // 方法2，dp是一个一维数组，dp[i]只受dp[i-1]一个因素影响，可以用一个整型变量维护dp
        int dp = nums[0];
        int result = nums[0];

        for(int i=1; i<nums.size(); ++i){
            dp = max(dp + nums[i],nums[i]);
            result = max(result, dp);
        }
        return result;
    }
};


int main(){
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    Solution_1 s;
    int outcome = s.maxSubArray(nums);
    cout<<outcome;
}